package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/4 21:43
 */
public class J37 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public static class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            preSerialize(root, sb);
            return sb.deleteCharAt(sb.length()-1).toString();
        }

        private void preSerialize(TreeNode head, StringBuilder sb) {
            if(head == null) {
                sb.append("null,");
            }else {
                sb.append(head.val + ",");
                preSerialize(head.left, sb);
                preSerialize(head.right, sb);
            }
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if(data == null || data.length()==0) {
                return null;
            }
            String[] nodes = data.split(",");
            index = 0;
            return preDes(nodes);
        }
        int index;
        private TreeNode preDes(String[] nodes) {
            if(nodes[index].equals("null")) {
                return null;
            }
            TreeNode cur = new TreeNode(Integer.parseInt(nodes[index]));
            index++;
            cur.left = preDes(nodes);
            index++;
            cur.right = preDes(nodes);
            return cur;
        }
    }

    // for test
    public static void main(String[] args) {
        Codec codec = new Codec();

        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(9);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(10);

        String s = codec.serialize(root);
        System.out.println(s);
        TreeNode head = codec.deserialize(s);
        prePrint(head);
    }

    private static void prePrint(TreeNode head) {
        if(head == null) {
            return;
        }
        System.out.print(head.val+ " ");
        prePrint(head.left);
        prePrint(head.right);
    }


}
